The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One such protocol is the link state protocol which relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. In some instances two paths have equal cost, termed an equal cost multi-path (ECMP) or path split. In those circumstances the node will forward down one or the other path dependent on some predetermined rule, for example to achieve load balancing between the paths. When there is a network topology change an LSP representing the change is flooded through the network by each node adjacent the change, each node receiving the LSP sending it to each adjacent node. The nodes each recomputed their SPF based on the changed topology and “converge” on the new topology.
The Network Time Protocol (NTP) is used to synchronize the clocks of computer systems over packet-switched, variable-latency data networks. Internet services often rely on accurate computer clocks, for example, when receiving a request to send a file modified after a certain time. For the purposes of maintaining consistent time-stamping, there is the requirement that computers sharing files from the same file server utilize synchronized clocks.
NTP employs a hierarchy of servers each with a designated stratum level. The stratum level defines the distance from and accuracy of the reference clock, a lower level being more favorable. NTP enables each server to synchronize to Universal Coordinated Time (UTC) using the most accurate source and shortest path to that source. It is preferable to have access to several sources of lower stratum time in order to detect error from any of the sources. Ordinarily, when the NTP servers are in agreement, NTP will choose the source with the combination of lowest stratum and transmission delay and highest claimed precision.
Currently, service providers are increasingly required to provide a much higher precision clock to some of their customers. NTP was designed on the basis that it was unable to influence the network between the clock source and the clock user. Where the service provider owns both the clock source and the delivery network, a solution may be deployed that utilizes the network to enhance delivery of the clock.
There are two particular problems that all clock over packet transfer protocols face. A first issue is path reciprocity—without path reciprocity it is impossible to do true clock synchronization. Ideally, Time at node A, Ta=Time at node B, Tb. When A pings B (or vice versa), it is assumed that where Transmission delay from A to B=Delay_ab and Transmission delay from B to A=Delay_ba that Delay_ab=(Delay_ab+Delay_ba)/2, and Tb is set to Ta+Delay_ab accordingly. In other words to synchronize clocks taking into account the path delay it is assumed that the delay is the same in both directions. In fact in time transfer systems, it is necessary to correct for path delay between the server and the client as Tactual=Tmsg+Ttransmission.
There is no way to measure Ttransmission directly as Tactual would need to be known at both the server and the client. The simple approximation of Ttransmission=Troundtrip/2 (as discussed above) is not suitable as the forward and return paths may not be symmetric between the server and the client. This may be as a result of using asymmetric costs when generating the network topology or because Equal Cost Multi-Path (ECMP) paths exist where the flows are not reciprocal (forward path≠return path).
A second issue is clock phase transients as a result of network transients. For example where the network topology changes (i.e. a clock synchronization path fails), there will be a constant offset in the delivery time and no ‘normal’ delay packets will be delivered until the network re-converges on the changed topology. During this time, the client is said to be in holdover (it has no NTP synchronized clock source) and must run on its own local oscillator.
These problems are both addressable with assistance at the routing layer. Similar problems exist with other packet timing protocols such as IEEE 1588.
In order to provide a high quality clock service, a client needs to groom the incoming packet stream to determine whether the packet has been delayed en route. A delayed packet should not be used to operate the clock servo as this will introduce errors.
Therefore, there follows a need to provide router assistance for enhancing and safeguarding the delivery of the clock synchronization packets to clients, and providing an enhanced degree of immunity of the network timing paths to network topology changes.